1. Field of the Invention
The present invention relates to calculating equipment for solving systems of linear equations, parallel calculating equipment for solving systems of linear equations, and methods of parallel computation for solving systems of linear equations.
2. Description of the Related Art
The need for solving systems of linear equations at high speed frequently arises in numerical analysis of the finite element method and the boundary element method and other processes of technical calculation.
Among algorithms based on direct methods of solving systems of linear equations is Gauss elimination method based on bi-pivot simultaneous elimination, which is described in Takeo Murata, Chikara Okuni and Yukihiko Karaki, "Super Computer-Application to Science and Technology," Maruzen 1985 pp 95-96. The bi-pivot simultaneous elimination algorithm eliminates two columns at the same time by choosing two pivots at one step. It limits simultaneous elimination to two columns and the choice of pivots to partial pivoting by row interchanges. Furthermore it considers the speeding up of its process in terms of numbers of repetition of do-loops only.
If simultaneous elimination is not limited to two columns and extended to more than two columns, the corresponding algorithms will be hereafter called multi-pivot simultaneous elimination algorithms.
A similar algorithm to multi-pivot simultaneous elimination algorithms is described in Jim Armstrong, "Algorithm and Performance Notes for Block LU Factorization," International Conference on Parallel Processing, 1988, Vol. 3, pp 161-164. It is a block LU factorization algorithm intended to speed up matrix operations and should be implemented in vector computers or computers with a few multiplexed processors.
Therefore, according to prior art, there has not yet been developed Gauss elimination method or Gauss-Jordan elimination method which is based on multi-pivot simultaneous elimination and can be efficiently implemented in scalar computers and parallel computers.